一道其实很简单然而我还是瞄了题解的题

首先考虑二分答案

显然将小于 $mid$ 的赋为 $-1$，将大于等于 $mid$ 赋为 $1$

那么显然 $total = $ $[q_1, q_2]$ 最长后缀 $+$ 中间必选 $+$ $[q_3, q_4]$ 最长前缀

然后若 $total \ge 0$ 则 $check (mid)$ 返回 $true$

很好然后我就不会处理了

于是题解就说将每个 $mid$ 建一棵线段树，然后用主席树就不会 $MLE$（好吧原来本来是想建序列上的主席树的说当然并不可行

那么每次 $check$ 就在 $mid$ 号版本上的树查询即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const int MAXN = 2e04 + 10;
const int MAXLOG = 30;
const int MAXT = MAXN * MAXLOG;

const int INF = 0x3f3f3f3f;

int N, Q;
int a[MAXN], mapp[MAXN]= {0};
int q[5];

struct valueSt {
    int subsum;
    int lmax, rmax;

    valueSt () {
        subsum = 0;
        lmax = rmax = - INF;
    }
} ;
int ctree[MAXT]= {0};
int lson[MAXT]= {0}, rson[MAXT]= {0};
valueSt value[MAXT];
int nodes = 0;
valueSt maintain (valueSt A, valueSt B) {
    valueSt res;
    res.subsum = A.subsum + B.subsum;
    res.lmax = max (A.lmax, A.subsum + B.lmax);
    res.rmax = max (B.rmax, A.rmax + B.subsum);
    return res;
}
void build (int& root, int left, int right) {
    root = ++ nodes;
    value[root] = valueSt ();
    if (left == right) {
        value[root].subsum = value[root].lmax = value[root].rmax = 1;
        return ;
    }
    int mid = (left + right) >> 1;
    build (lson[root], left, mid);
    build (rson[root], mid + 1, right);
    value[root] = maintain (value[lson[root]], value[rson[root]]);
}
void update (int pre, int& root, int left, int right, int posi) {
    root = ++ nodes;
    lson[root] = lson[pre], rson[root] = rson[pre];
    value[root] = value[pre];
    if (left == right) {
        value[root].subsum = value[root].lmax = value[root].rmax = - 1;
        return ;
    }
    int mid = (left + right) >> 1;
    if (posi <= mid) update (lson[pre], lson[root], left, mid, posi);
    else update (rson[pre], rson[root], mid + 1, right, posi);
    value[root] = maintain (value[lson[root]], value[rson[root]]);
}
valueSt tans;
// 以下注意（以rmax为例）
// 由于query_sum是由左至右走，并且maintain中是取B的rmax或者将A与B合并
// 那么在query_sum中value[root]不可能作为B
// 故最终获得的tans.rmax的起始点一定为q[2]
void query_sum (int root, int left, int right, int L, int R) {
    if (L <= left && right <= R) {
        tans = maintain (tans, value[root]);
        return ;
    }
    int mid = (left + right) >> 1;
    if (L <= mid) query_sum (lson[root], left, mid, L, R);
    if (R > mid) query_sum (rson[root], mid + 1, right, L, R);
}

bool check (int mid) {
    int total = 0;
    if (q[2] + 1 <= q[3] - 1) {
        tans = valueSt (), query_sum (ctree[mid], 1, N, q[2] + 1, q[3] - 1);
        total += tans.subsum;
    }
    tans = valueSt (), query_sum (ctree[mid], 1, N, q[1], q[2]);
    total += tans.rmax;
    tans = valueSt (), query_sum (ctree[mid], 1, N, q[3], q[4]);
    total += tans.lmax;
    return total >= 0;
}

int ans = 0;

int comp (const int& x, const int& y) {
    return a[x] < a[y];
}

int getnum () {
    int num = 0;
    char ch = getchar ();
    bool isneg = false;

    while (! isdigit (ch)) {
        if (ch == '-') isneg = true;
        ch = getchar ();
    }
    while (isdigit (ch))
        num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();

    return isneg ? - num : num;
}

int main () {
    N = getnum ();
    for (int i = 1; i <= N; i ++)
        a[i] = getnum (), mapp[i] = i;
    sort (mapp + 1, mapp + N + 1, comp);
    build (ctree[1], 1, N);
    for (int i = 2; i <= N; i ++) {
        ctree[i] = ctree[i - 1];
        update (ctree[i - 1], ctree[i], 1, N, mapp[i - 1]);
    }
    Q = getnum ();
    for (int Case = 1; Case <= Q; Case ++) {
        for (int i = 1; i <= 4; i ++)
            q[i] = (getnum () + ans) % N + 1;
        sort (q + 1, q + 5);
        int left = 1, right = N;
        while (left <= right) {
            int mid = (left + right) >> 1;
            check (mid) ? (ans = a[mapp[mid]], left = mid + 1) : right = mid - 1;
        }
        printf ("%d\n", ans);
    }

    return 0;
}

/*
5
170337785
271451044
22430280
969056313
206452321
3
3 1 0 2
2 3 1 4
3 1 4 0
*/